{
    "cells": [
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "import numpy  as np\n",
                "import matplotlib.pyplot as plt\n",
                "%matplotlib inline\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## A\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "In this part we  generate 1000 pairs of random vectors, compute the angle in each pair, and plots the corresponing histogram.\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "**Complete the code in this part of the notebook and observe the histograms. Report how many of sampled angles fall out of the interval that you computed in part b of the problem (in pdf). Would you consider the theoretical bounds tight?**\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "d = 400\n",
                "angles = []\n",
                "for _ in range(1000):\n",
                "    x = np.random.randn(d)\n",
                "    y = np.random.randn(d)\n",
                "    #TODO compute the angle between vectors x and y\n",
                "    ### start a1 ###\n",
                "\n",
                "    ### end a1 ###\n",
                "    angles += [angle]\n",
                "\n",
                "\n",
                "plt.hist(angles, bins=20)\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "#TODO: compute how many elements of array 'angles' lie outside of the numerical interval that\n",
                "#you found in part b of the problem\n",
                "### start a2 ###\n",
                "\n",
                "### end a2 ###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## B\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Now we look how good our bounds on singular values are. In the following cells compute the histograms of the maximum and minimum squared singular values of $\\bf{X}$ over 100 independent generations, where $\\bf{X}$ is a $10\\times 1000$ matrix with i.i.d. standard normal entries.\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "***Complete the code in this part and observe the histograms. Report how close the numbers that you observe are to the theoretical bounds which you computed in part e of the problem (in pdf).***\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "sigma_max_squared_vals = []\n",
                "sigma_min_squared_vals = []\n",
                "for _ in range(100):\n",
                "    X = np.random.randn(10, 1000)\n",
                "    #TODO: compute the minimum and maximum singular values of X: sigma_min and sigma_max\n",
                "    ### start b ###\n",
                "\n",
                "    ### end b ###\n",
                "    sigma_max_squared_vals += [sigma_max**2]\n",
                "    sigma_min_squared_vals += [sigma_min**2]\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "plt.hist(sigma_max_squared_vals)\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "plt.hist(sigma_min_squared_vals)\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## C\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "In this part we will check what is the right order of magnitude for the smallest singular value of an $n\\times n$ matrix with i.i.d. standard normal entries. We will look at several different values of $n$, and for each of them we will sample $\\bf{X}$ 100 times and compute the average of the singular values. Then we will find the right power of the dependence of $\\sigma_{\\min}$ on $n$ by looking at the log-log plot and fitting a linear function.\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "**Complete the code in this part. What is the right scale of $\\sigma_{\\min}$ in terms of $n$? Does it confirm the intuition that we developed in part h of the problem, or was assuming independence of different upper bound too reckless?**\n",
                "\n",
                "*HINT: imagine $\\sigma_{\\min} = 1/n$. What would be the slope of the line if you plotted $\\log \\sigma_{\\min} $ against $\\log n$?*\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "sigmamins = []\n",
                "n_range = range(100, 1100, 100)\n",
                "for n in n_range:\n",
                "    sigmamins_batch = []\n",
                "    for _ in range(100):\n",
                "        X = np.random.randn(n,n)\n",
                "        #TODO compute the minimum singular value of X\n",
                "        ### start c ###\n",
                "\n",
                "        ### end c ###\n",
                "        sigmamins_batch += [sigma_min]\n",
                "\n",
                "    sigmamins += [np.mean(sigmamins_batch)]\n",
                "\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "from sklearn.linear_model import LinearRegression\n",
                "def solve_ls(phi, y):\n",
                "    LR = LinearRegression(fit_intercept=False, normalize=False)\n",
                "    LR.fit(phi, y)\n",
                "    coeffs = LR.coef_\n",
                "    return coeffs\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "# augment np.log(n_range) with ones to learn affine function\n",
                "Phi = np.vstack((np.log(n_range), np.ones(len(n_range))))\n",
                "\n",
                "# find the affine function with linear regression\n",
                "coeffs = solve_ls(Phi.T, np.log(sigmamins))\n",
                "\n",
                "plt.plot(np.log(n_range), np.log(sigmamins), label = 'true $\\sigma_{\\min}$')\n",
                "plt.plot(np.log(n_range), Phi.T @ coeffs, label = 'fitted linear dependence')\n",
                "plt.xlabel('log n')\n",
                "plt.ylabel('log $\\sigma_{\\min}$')\n",
                "plt.legend()\n",
                "print(coeffs)\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": []
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "Python 3",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.7.4"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}